1. Field of the Invention
This application claims priority from and is a continuation of U.S. patent application Ser. No. 09/851,940, filed May 10, 2001, now U.S. Pat. No. 6,970,171, the entire contents of which are herein incorporated by reference for all purposes.
2. Description of the Related Art
Traditional animation techniques allow the animator to create the apparent motion of animated characters, to be viewed by a viewer of the animation. The use of computers to simplify the animation process has provided many benefits to the traditional hand-drawn process. Computer animated characters are well known in the prior art and have been used in many different capacities. Such characters are utilized in traditional movies, videos and online streaming of moving pictures, as well as interactive movies where the motion of characters is often initiated by a user.
Often times in the animation of characters, the characters have “secondary elements”, such as clothing and hair, that are responsive to the main motion of the characters. Computer animation routinely employs physically-based numerical simulation methods to automatically produce motions for these complex secondary objects, such as clothing and hair. Determining an object's response to collisions is one of the most important aspects of this type of simulation. A simulated shirt on a human character, for example, needs to react to collisions with the character's body. The shirt must also react to collisions with itself (self-collisions) as the shirt wrinkles and folds, and to collisions with other articles of clothing (e.g. pants or a jacket).
A motion simulator with a good collision-response algorithm tries to generate motion that is devoid of intersections (motions of objects through other objects). Unfortunately, this may not always be possible, and the simulator must be prepared to deal with intersections if they occur. Simulated clothing for example, should not self-intersect as it wrinkles and folds. However, no prior art collision-response algorithm for cloth is perfect; the cloth will sometimes self-intersect despite a simulator's best efforts. When this happens, it is vital for the motion simulation algorithm to analyze and understand the nature of the intersection and then generate a response that quickly removes the intersection. The end result is an intersection that is limited to a hopefully tolerable duration.
Intersections also occur that are inherently unavoidable: it is common for animators to pose characters so that they self-intersect. For example, a character crossing her arms over her torso may actually have the arm penetrating into the torso to achieve a tight pose, as illustrated in FIGS. 1a and 1b. This self-intersection occurs for two main reasons. First, the animator may be unaware that intersection has occurred, because the intersection may not be visible from the virtual camera the animator uses to view the scene. Second, limitations in the controls for posing the character may force the animator into using poses that result in self-intersection, to achieve the desired look.
When this happens, the animator will arrange the characters so that the necessary self-intersections are not visible from the camera's point of view (contrast FIG. 1a with FIG. 1b). However, if the character is wearing simulated clothing, the character's self-intersections force the simulated clothing, which is caught between intersecting body parts, to intersect both itself and the character. This is a serious problem for the motion simulation program which must choose a best-course action which yields reasonable motion behavior for the simulated clothing, even in the presence of potentially large intersections.
The prior art systems fail to adequately solve such problems. As a result, if the simulated object's motion behavior is not reasonable, then these undesirable results must be corrected by the animator directly. In such cases, the simulator, designed to ease the burden on the animator by having associated objects react to the motion of the character automatically, places the burden back on the animator to correct for the improper results. As such, there is a need in the prior art to have improved processes that allow the for proper simulation of computer-displayed objects even in the face of intersections between the objects.
There have been attempts to do the type of analysis needed to address the above-noted problems. In particular, “Versatile and Efficient Techniques for Simulating Cloth and Other Deformable Objects”, P. Volino et al., Computer Graphics, SIGGRAPH '95 proc., pp. 137-144, 1995, details a method for detecting self collisions and determining the inside-outside orientation in those collisions.
However, this work has several drawbacks as discussed below. First, the method depends heavily on “history.” In other words, at time t0, the method uses information about the cloth positions at times t<t0 (i.e. the “past”) to make decisions about what to do at time t0. In particular, the assumption is made that past states are always correct, so that if a cloth particle was above a cloth surface in the past, but is now below it, then being above is the correct state, and being below it is wrong.
In addition, in section 3.2.1 of the above-cited paper, the authors also attempt to examine the cloth in a small neighborhood near the intersection of an edge through a face, as a part of the method. The system takes a majority vote to determine which side is the correct side for the cloth to be on. However, this is a local examination, not a global one. Thus intersections outside of this small neighborhood are not considered. Additionally, the method of the cited paper relies only on statistics; their method forces the cloth to choose “yes, I'm right” or “no, I should be on the other side.” Such a system allows each portion of the cloth to have an equal weight and thus the portions that have the “wrong” orientation effect the determination as much as those portions that have the “correct” orientation.